class Solution {
    public void solveSudoku(char[][] board) {
        this.board = board;
        init();
        fill();
        board = this.board;
    }
    private boolean fill() {
        Pair<Integer, Integer> location = getLeastPossibleLocation();
        int x = location.getKey();
        int y = location.getValue();
        if (x == -1) {
            return true;
        }
        for (int i = 1; i < 10; i++) {
            if (!row[x][i] && !col[y][i] && !box[x/3*3+y/3][i]) {
                board[x][y] = (char)('0'+i);
                row[x][i] = true;
                col[y][i] = true;
                box[x/3*3+y/3][i] = true;
                if (fill()) return true;
                box[x/3*3+y/3][i] = false;
                col[y][i] = false;
                row[x][i] = false;
                board[x][y] = '.';
            }
        }
        return false;
    }
    private Pair<Integer, Integer> getLeastPossibleLocation() {
        int ansCnt = 10;
        Pair<Integer, Integer> pair = new Pair<>(-1, -1);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                int cnt = 0;
                for (int k = 1; k <= 9; k++) {
                    if (!row[i][k] && !col[j][k] && !box[i/3*3+j/3][k]) {
                        cnt++;
                    }
                }
                if (cnt < ansCnt) {
                    ansCnt = cnt;
                    pair = new Pair<>(i, j);
                }
            }
        }
        return pair;
    }
    private Pair<Integer, Integer> getFirstEmpytLocation() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    return new Pair<>(i,j);
                }
            }
        }
        return new Pair<>(-1,-1);
    }
    private void init() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                char ch = board[i][j];
                if (ch == '.') {
                    continue;
                }
                int idx = ch - '0';
                row[i][idx] = true;
                col[j][idx] = true;
                box[i/3*3+j/3][idx] = true;
            }
        }
    }
    private char[][] board;
    private boolean[][] row = new boolean[9][10];
    private boolean[][] col = new boolean[9][10];
    private boolean[][] box = new boolean[9][10];
}
